#include <stdio.h>
#include <stdlib.h>


struct ListNode {
    int val;
    struct ListNode* next;
};

//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    struct ListNode* li1 = list1;
//    struct ListNode* li2 = list2;
//    struct ListNode* cur=list1;
//    struct ListNode* ret = list1;
//
//    while (li1 && li2)
//    {
//        if (li1->val <li2->val)
//        {
//            cur->val = li1->val;
//            cur = cur->next;
//            li1 = li1->next;
//        }
//        else
//        {
//            cur->val = li2->val;
//
//            cur = cur->next;
//            li2 = li2->next;
//        }
//    }
//
//    return cur;
//
//
//}







struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* li1 = list1;
    struct ListNode* li2 = list2;
    struct ListNode* next1;
    struct ListNode* next2;
    int count = 0;
    while (li1 && li2)
    {
        next1 = li1->next;
        next2 = li2->next;
        if (li2->val <= li1->val)
        {
            if (count >= 1)
            {
                li2->next = li1;
                li2 = next2;
            }
            count++;
            li2->next = li1;
            li2 = next2;
        }
        else
        {
            li1 = next1;
        }
    }
    if (!list1)
        return list2;
    else
        return list1;


}



struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* nextnode = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* head = nextnode;
    struct ListNode* cur = nextnode;
    if (!list1)
        return list2;
    else if (!list2)
        return list1;
    else
    {
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                cur->next = list1;
                cur = cur->next;
                list1 = list1->next;
                cur->next = NULL;
            }
            else
            {
                cur->next = list2;
                cur = cur->next;
                list2 = list2->next;
                cur->next = NULL;
            }
        }
        if (list1)
            cur->next = list1;
        if (list2)
            cur->next = list2;
        return head->next;
    }
}






int main()
{
    struct ListNode* list1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    list1->val = 1;
    n2->val = 2;
    n3->val = 4;

    list1->next = n2;
    n2->next = n3;
    n3->next = NULL;

    struct ListNode* list2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* a2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* a3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* a4 = (struct ListNode*)malloc(sizeof(struct ListNode));

    list2->val = 1;
    a2->val = 3;
    a3->val = 4;

    list2->next = a2;
    a2->next = a3;
    a3->next = NULL;

    struct ListNode* ret=mergeTwoLists(list1, list2);
    return 0;
}
